package com.mgq.algorithm.array;

import java.util.Arrays;

/**
 * @author MaGuangQi
 * 归并排序
 * @date 2021-12-27 09:19
 **/
public class MergeSort {
    public static void main(String[] args) {
        int[] array = {1,65,34,34,5,3,223,5768,53,22,3};
         process(array, 0, array.length - 1);

    }

    public static void process(int[] array,int L,int R) {
        if (L == R) {
            return ;
        }
        int mid=L+((R-L)>>1);
        process(array,L,mid);
        process(array,mid+1,R);
        merge(array,L,mid,R);
        System.out.println(Arrays.toString(array));
    }

    private static void merge(int[] array, int L, int mid, int R) {
        //准备一个help数组,大小为元素的个数
        int[] help = new int[R - L + 1];
        //help的指针
        int i=0;
        //左侧指针
        int p1=L;
        //右侧指针
        int p2=mid+1;
        //不越界
        while (p1 <= mid && p2 <= R) {
            //把最小的复制到help
            help[i++]=array[p1]<array[p2]?array[p1++]:array[p2++];
        }
        //只要出了for循环,肯定是某一个发生了越界,只需要把剩下的复制过去即可
        while (p1 <= mid) {
            help[i++] = array[p1++];
        }
        //p2没有越界
        while (p2 <= R) {
            help[i++] = array[p2++];
        }
        //将help复制到arr
        for (int j = 0; j < help.length; j++) {
            array[L+j] = help[j];
        }
    }
}
